// poj2154
// 题意：给定n(<=10^9)个颜色，要将一个有n个珠子的圆环项链染色，可以不用
//       完所有颜色，经过旋转相同的染色方案不重复算，问有多少本质不同的
//       染色方案，输出模除p(1<=p<=30000)。
//
// 题解：肯定是 Pólya 定理。对于包含m个对象的置换群G(X, g)，X是对象集合，
//       g是其中的一个置换。Y是一个有限的颜色集，|Y|=k。用这些种颜色给
//       这m个对象染色，本质不同的方案数为：
//         |Y^X/G|=(1/|G|)*sigma(k^c(g))
//       c(g)是置换g的循环指标，循环节个数。
//
//       首先对于原n个圆形排列的珠子，任意方向旋转i个珠子所对应群的
//       c(g)=gcd(n, i)，每个循环的长度l=n/gcd(n, i)。
//       这样就有了一个O(n)的算法，枚举i然后算答案。
//       但是n太大，我们可以考虑枚举l，及任意li | n，然后算有多少个i
//       使得gcd(n, i)=n/li。
//       我们令t=n/li, 再令i=a*t。则n=li*t。
//       那么gcd(i, n)=t的充要条件是gcd(a, li)=1。而gcd(a, li)=1的个数
//       就是phi(li)。
//
//       这样我们就有了一个O(sqrt(n))的算法，枚举n的因子，然后算对应li
//       的欧拉函数，再算答案。
//
// run: $exec < input
#include <cstdio>
#include <vector>

int const maxn = 36000;
bool not_prime[maxn];
int n, p;

int prime[maxn];
int len;

void init_prime()
{
	for (int i = 2; i < maxn; i++) {
		if (not_prime[i]) continue;
		prime[len++] = i;
		for (int j = 2 * i; j < maxn; j += i)
			not_prime[j] = true;
	}
}

int quick_pow(int a, int b, int p)
{
	if (!b) return 1 % p;
	int tmp = quick_pow(a, b / 2, p);
	tmp = (tmp * tmp) % p;
	if (b & 1) tmp = (tmp * a) % p;
	return tmp;
}

int phi(int x)
{
	if (x == 1) return 1;
	int ret = x;
	for (int i = 0; i < len && prime[i] * prime[i] <= x; i++) {
		if (x % prime[i]) continue;
		ret -= ret / prime[i];
		while (!(x % prime[i])) x /= prime[i];
		if (x == 1) break;
	}
	if (x != 1) ret -= ret / x;
	return ret;
}

int main()
{
	init_prime();
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &p);
		int tn = n % p;
		int ans = 0;
		for (int l = 1; l * l <= n; l++) {
			if (n % l) continue;
			int tmp = n / l;
			int num = phi(l) % p;
			ans = (ans + (quick_pow(tn, tmp - 1, p) * num) % p) % p;
			if (n / l == l) continue;
			tmp = l;
			num = phi(n / l) % p;
			ans = (ans + (quick_pow(tn, tmp - 1, p) * num) % p) % p;
		}
		std::printf("%d\n", ans);
	}
}

